package Algoritmo;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.PriorityQueue;
import java.util.Random;

public class AlgoritmoGenetico {
	final static double  Beta_ = 1.5;
	
	int tamPoblacion;
	int idSeleccion,idPoblacion;
	Cromosoma[] poblacion;
	Cromosoma[] nuevaPoblacion;
	double probCruce;
	double probMutacion;
	int posMejor;
	Cromosoma mejor;
	Cromosoma mejorPorGeneracion;
	int tamElite;
	int profundidad,penalizacion,numPartidas;
	double total;
	ArrayList<Cromosoma> elite;
	ArrayList<Integer> posElite;
	int numMaxGeneraciones;
	double[] minGlobal;
	double[] minPorGeneracion;
	double[] media;
	String sSeleccion,sPoblacion;
	int totalMutaciones,totalCruces;
	Comparator<Cromosoma> miComp;
	
	public AlgoritmoGenetico(){
		this.tamPoblacion = 100;
		this.numMaxGeneraciones = 100;
		this.probCruce = 0.7;
		this.probMutacion = 0.02;
		this.tamElite = 0;
		this.idSeleccion = 0;
		this.sSeleccion = "Ruleta";
		this.sPoblacion = "Creciente-Completa";
		this.profundidad = 3;
		this.numPartidas = 30;
		this.penalizacion = 200;
		miComp = new Comparator<Cromosoma>(){
			public int compare(Cromosoma n1,Cromosoma n2){
				double x = n1.getF();
				double y = n2.getF();
				if(x < y) return -1;
				else if (x > y) return 1;
				return 1;
			};
		};
	}
	
	public void clear(){
		this.poblacion = null;
		this.nuevaPoblacion = null;
		this.elite = null;
		this.posElite = null;
		this.mejor = null;
		this.mejorPorGeneracion = null;
		this.minGlobal = null;
		this.minPorGeneracion = null;
		this.media = null;
	}
	
	public void inicializacion(){
		this.poblacion = new Cromosoma[tamPoblacion];
		this.nuevaPoblacion = new Cromosoma[tamPoblacion];
		this.elite = new ArrayList<Cromosoma>();
		this.posElite = new ArrayList<Integer>();
		this.idSeleccion = getIdSeleccion();
		this.idPoblacion = getIdPoblacion();
		this.minGlobal = new double[numMaxGeneraciones];
		this.minPorGeneracion = new double[numMaxGeneraciones];
		this.media = new double[numMaxGeneraciones];
		this.total = 0;
		this.totalCruces = 0;
		this.totalMutaciones = 0;
	}
	
	private void inicializarPoblacion(Cromosoma[] poblacion){
		switch(idPoblacion){
			case 0: inicializarPoblacionCompleta(poblacion);
				break;
			case 1: inicializarPoblacionConjuntos(poblacion);
				break;
		}
	}
	
	private void inicializarPoblacionCompleta(Cromosoma[] poblacion){
		if (tamPoblacion == 0) return;
		double min = Double.MAX_VALUE;
		double max = Double.MIN_VALUE;
		for (int i=0;i<tamPoblacion;i++){
			poblacion[i] = new Cromosoma(profundidad,profundidad,numPartidas,penalizacion);
			poblacion[i].inicializacion();
			double f = poblacion[i].getF();
			if (f < min) min = f;
			if (f > max) max = f;
		}
	}
	
	private void inicializarPoblacionConjuntos(Cromosoma[] poblacion){
		int numConjuntos = 3;
		int[] numIndPorConj = new int[3];
		asignarNumIndividuosParaConjuntos(numIndPorConj,numConjuntos);
		int ini = 0;
		for (int i=0;i<numConjuntos;i++){
			int n = numIndPorConj[i];
			int m = n/2; 
			for(int j=ini; j<ini+m;j++){
				poblacion[j] = new Cromosoma(i+1,profundidad,numPartidas,penalizacion);
				poblacion[j].inicializacion();
			}
			for(int j=ini+m; j<ini+n;j++){
				poblacion[j] = new Cromosoma(profundidad,profundidad,numPartidas,penalizacion);
				poblacion[j].inicializacion();
			}
			ini = ini + n;
		}
	}
	
	private void adaptarPoblacion(Cromosoma[] poblacion){
		double t = 0;
		for(int i=0;i<tamPoblacion;i++){
			t = t + poblacion[i].getF();
		}
		total = t;
	}
	
	private void evaluarPoblacion(Cromosoma[] poblacion){
		double acu = 0;
		int _posMejor = 0;
		double mejorValor = Double.MAX_VALUE;
		for (int i=0;i<tamPoblacion;i++){
			double f = poblacion[i].getF();
			double puntuacion = f / total;
			acu = acu + puntuacion;
			poblacion[i].setPuntuacion(puntuacion);
			poblacion[i].setPuntuacion_acu(acu);
			if (poblacion[i].getF() < mejorValor){
				_posMejor = i;
				mejorValor = poblacion[i].getF();
			}
		}
		this.mejorPorGeneracion = poblacion[_posMejor].clone();
		this.posMejor = _posMejor;
		this.obtenerElMejorGlobal(poblacion,_posMejor);
	}
	
	private void separarElite(int posMejor,Cromosoma[] poblacion){
		if(!elitismo())return;
		if(posElite.size()>0) posElite.clear();
		if(elite.size()>0) elite.clear();
		if(tamElite == 1){
			posElite.add(posMejor);
			elite.add(poblacion[posMejor].clone());
			return;
		}
		HashMap<Cromosoma,Integer> map = new HashMap<Cromosoma,Integer>(); 
		
		PriorityQueue<Cromosoma> monticulo = new PriorityQueue<Cromosoma>(tamPoblacion,miComp);
		for(int i=0;i<tamPoblacion;i++){
			Cromosoma p = poblacion[i].clone();
			map.put(p,i);
			monticulo.add(p);
		}
		for(int i=0;i<tamElite;i++){
			Cromosoma c = monticulo.poll();
			posElite.add(map.get(c));
			elite.add(c);
		}
	}
	
	private void addElite(Cromosoma[] poblacion){
		if (!elitismo()) return;
		int tam = tamPoblacion - tamElite;
		int k = tam;
		for(Iterator<Cromosoma> it=elite.iterator();it.hasNext() && k<tamPoblacion;){
			Cromosoma c = it.next();
			poblacion[k] = c;
			k = k+1;
		}
	}
	
	private void seleccionRuleta(Cromosoma[] poblacion){
		int tam = tamPoblacion - tamElite;
		int[] seleccionados = new int[tam];
		int i = 0;
		Random r = new Random(1);
		while (i<tam){
			int pos_super = 0;
			double prob = r.nextFloat();
			while (prob > poblacion[pos_super].getPuntuacion_acu() && pos_super < tamPoblacion)
				pos_super ++ ;
			seleccionados[i] = pos_super;
			i++;
		}
		nuevaPoblacion = new Cromosoma[tamPoblacion];
		for(int j=0;j<tam;j++){
			nuevaPoblacion[j] = poblacion[seleccionados[j]].clone();
		}
	}
	
	private void seleccionTorneoDeterminista(Cromosoma[] poblacion){
		int tam = tamPoblacion - tamElite;
		int[] seleccionados =  new int[tam];
		int i = 0;
		int pos_super = 0;
		Random r = new Random();
		while(i < tam){
			int index1 = 0;
			int index2 = 0;
			index1 = r.nextInt(tamPoblacion);
			index2 = r.nextInt(tamPoblacion);
			
			while(index1 == index2) index2 = r.nextInt(tamPoblacion);
			
			pos_super = (poblacion[index1].getF() < poblacion[index2].getF()) ? index1 : index2;
			seleccionados[i] = pos_super;
			i++;
		}
		
		nuevaPoblacion = new Cromosoma[tamPoblacion];
		for (int j=0;j<tam;j++){
			nuevaPoblacion[j] = poblacion[seleccionados[j]].clone();
		}
	}
	
	private void performRankSelection(Cromosoma[] initPop) {
			Cromosoma[] sortedPop = SortCromosoma(initPop);
			int tam = tamPoblacion - tamElite;
			nuevaPoblacion = new Cromosoma[sortedPop.length];
			nuevaPoblacion[0] = sortedPop[0].clone();
			nuevaPoblacion[1] = sortedPop[1].clone();
			int numOfParents = 2;
			double[] fitnessSegments = rankPopulation();
			double entireSegment = fitnessSegments[fitnessSegments.length - 1]; 
		
			while(numOfParents < tam){
				double x = (double)(Math.random() * entireSegment);
				if(x <= fitnessSegments[0]) {
					/*** First Idividual was Selected **/
					nuevaPoblacion[numOfParents] = sortedPop[0].clone();
					numOfParents++;
				}
				else
					for(int i = 1; i < nuevaPoblacion.length; i++)
						if(x > fitnessSegments[i - 1] && x <= fitnessSegments[i]){
							/*** i'th Idividual was Selected **/
							nuevaPoblacion[numOfParents] = sortedPop[i].clone();
							numOfParents++;
						}
			}
			
		}

	private Cromosoma[] SortCromosoma(Cromosoma[] initPop) {
			PriorityQueue<Cromosoma> monticulo = new PriorityQueue<Cromosoma>(tamPoblacion,miComp);
			for (int i = 0; i < initPop.length; i++)			
				monticulo.add(initPop[i]);
			
			Cromosoma[] sortCromosoma = new Cromosoma[initPop.length];
			for (int i = 0; i < initPop.length; i++)
				sortCromosoma[i] = monticulo.poll();
			
			return sortCromosoma;
		}

	private double[] rankPopulation(){
		double[] fitnessSegments = new double[tamPoblacion];
		
		for(int i = 0 ; i < fitnessSegments.length ; i++){
			double probOfIth = (double)i / tamPoblacion; 
			probOfIth = probOfIth * 2 * (Beta_ - 1);
			probOfIth = Beta_ - probOfIth;
			probOfIth = (double)probOfIth * ((double)1 / tamPoblacion);
			
			if(i != 0)
				fitnessSegments[i] = fitnessSegments[i - 1] + probOfIth;
			else
				fitnessSegments[i] = probOfIth;
		}
		return fitnessSegments;
	}
	
	private void seleccion(Cromosoma[] poblacion){
		switch(idSeleccion){
			case 0: seleccionRuleta(poblacion);
				break;
			case 1: seleccionTorneoDeterminista(poblacion);
				break;
			case 2: performRankSelection(poblacion);
				break;
		}
	}
	
	private void reproduccion(){
		int tam = tamPoblacion - tamElite;
		int[] seleccionados_cruce = new int[tam];
		int num = 0;
		double prob = 0.0;
		Random r = new Random();
		for(int i=0;i<tam;i++){
			prob = r.nextDouble();
			if (prob < probCruce){
				seleccionados_cruce[num] = i;
				num = num + 1;
			}
		}
		if(num%2 == 1) num = num -1;
		if (num <= 0) return;
		totalCruces = totalCruces + num / 2;
		for (int i=0;i<num-1;i = i+2){
			Cromosoma p1 = nuevaPoblacion[seleccionados_cruce[i]].clone();
			Cromosoma p2 = nuevaPoblacion[seleccionados_cruce[i+1]].clone();
			Cromosoma[] hijos = Cruce.cruce(p1,p2);
			nuevaPoblacion[seleccionados_cruce[i]] = hijos[0];
			nuevaPoblacion[seleccionados_cruce[i+1]] = hijos[1];
		}
	}
	
	private void mutacion(){
		int tam = tamPoblacion - tamElite;
		Random r = new Random();
		double prob = 0.0;
		for(int i=0;i<tam;i++){
			prob = r.nextDouble();
			if(prob < probMutacion){
				Cromosoma c = Mutacion.mutacion(nuevaPoblacion[i].clone());
				nuevaPoblacion[i] = c;
				totalMutaciones ++;
			}
		}
	}
	
	private void recopilarDatosDeLaGeneracion(Cromosoma[] nuevaPoblacion,int numGeneraciones){
		this.minGlobal[numGeneraciones] = this.mejor.getF();
		this.minPorGeneracion[numGeneraciones] = this.mejorPorGeneracion.getF();
		this.media[numGeneraciones] = this.mediaDeLaGeneracion(nuevaPoblacion, tamPoblacion);
	}
	
	public void algoritmo_genetico(){
		inicializarPoblacion(poblacion);
		adaptarPoblacion(poblacion);
		evaluarPoblacion(poblacion);
		int numGeneraciones = 0;
		while (numGeneraciones < numMaxGeneraciones){
			if(numGeneraciones == 0 ) separarElite(this.posMejor, poblacion);
			else separarElite(this.posMejor, nuevaPoblacion);
			if(numGeneraciones == 0 )seleccion(poblacion);
			else seleccion(nuevaPoblacion);
			reproduccion();
			mutacion();
			addElite(nuevaPoblacion);
			adaptarPoblacion(nuevaPoblacion);
			recopilarDatosDeLaGeneracion(nuevaPoblacion, numGeneraciones);
			evaluarPoblacion(nuevaPoblacion);
			numGeneraciones++;
		}
	}
	
	public boolean terminado(){
		return nuevaPoblacion != null && nuevaPoblacion.length > 0;
	}
	
	public int getTamPoblacion() {
		return tamPoblacion;
	}

	public void setTamPoblacion(int tamPoblacion) {
		this.tamPoblacion = tamPoblacion;
	}

	public double getProbCruce() {
		return probCruce;
	}

	public void setProbCruce(double probCruce) {
		this.probCruce = probCruce;
	}

	public double getProbMutacion() {
		return probMutacion;
	}

	public void setProbMutacion(double probMutacion) {
		this.probMutacion = probMutacion;
	}

	public Cromosoma getMejor() {
		return mejor;
	}

	public void setMejor(Cromosoma mejor) {
		this.mejor = mejor;
	}

	public int getTamElite() {
		return tamElite;
	}

	public void setTamElite(int tamElite) {
		this.tamElite = tamElite;
	}

	public int getProfundidad() {
		return profundidad;
	}

	public void setProfundidad(int profundidad) {
		this.profundidad = profundidad;
	}
	public int getPenalizacion() {
		return penalizacion;
	}

	public void setPenalizacion(int penalizacion) {
		this.penalizacion = penalizacion;
	}

	public int getNumPartidas() {
		return numPartidas;
	}

	public void setNumPartidas(int numPartidas) {
		this.numPartidas = numPartidas;
	}

	public int getNumMaxGeneraciones() {
		return numMaxGeneraciones;
	}

	public void setNumMaxGeneraciones(int numMaxGeneraciones) {
		this.numMaxGeneraciones = numMaxGeneraciones;
	}

	public int getTotalCruces() {
		return totalCruces;
	}
	
	public void setTotalCruces(int totalCruces) {
		this.totalCruces = totalCruces;
	}
	
	public int getTotalMutaciones() {
		return totalMutaciones;
	}
	
	public void setTotalMutaciones(int totalMutaciones) {
		this.totalMutaciones = totalMutaciones;
	}
	
	public double[] getMinGlobal() {
		return minGlobal;
	}

	public void setMinGlobal(double[] minGlobal) {
		this.minGlobal = minGlobal;
	}

	public double[] getMinPorGeneracion() {
		return minPorGeneracion;
	}

	public void setMinPorGeneracion(double[] minPorGeneracion) {
		this.minPorGeneracion = minPorGeneracion;
	}

	public double[] getMedia() {
		return media;
	}

	public void setMedia(double[] media) {
		this.media = media;
	}

	public String getsSeleccion() {
		return sSeleccion;
	}

	public void setsSeleccion(String sSeleccion) {
		this.sSeleccion = sSeleccion;
	}
	
	public String getsPoblacion() {
		return sPoblacion;
	}
	
	public void setsPoblacion(String sPoblacion) {
		this.sPoblacion = sPoblacion;
	}

	public double[] getArrayGeneraciones(){
		double[] g = new double[numMaxGeneraciones];
		for(int i=0;i<numMaxGeneraciones;i++)
			g[i] = i+1;
		return g;
	}
	
	private int getIdSeleccion(){
		switch(sSeleccion){
			case "Ruleta": return 0;
			case "Torneo": return 1;
			case "Ranking": return 2;
		}
		return 0;
	}
	
	private int getIdPoblacion(){
		switch(sPoblacion){
			case "Completa" : return 0;
			case "Creciente-Completa": return 1;
		}
		return 1;
	}
	
	private void obtenerElMejorGlobal(Cromosoma[] poblacion,int _posMejor){
		if (mejor == null){
			mejor = poblacion[_posMejor].clone();
			return;
		}
		if (poblacion[_posMejor].getF() < mejor.getF()){
			mejor = poblacion[_posMejor].clone();
		}
	}
	
	private boolean elitismo(){
		return tamElite > 0;
	}
	
	private void asignarNumIndividuosParaConjuntos(int[] numIndPorConj, int numConjuntos){
		int mod = tamPoblacion % numConjuntos;
		int n = tamPoblacion / numConjuntos;
		for (int i=0; i<numConjuntos; i++){
			numIndPorConj[i] = n;
		}
		numIndPorConj[numConjuntos-1] = numIndPorConj[numConjuntos-1] + mod; 
	}
	
	private double mediaDeLaGeneracion(Cromosoma[] poblacion,int tamPoblacion){
		double media = 0;
		for (int i=0;i<tamPoblacion;i++){
			media = media + poblacion[i].getF();
		}
		return media/tamPoblacion;
	}
}
